GATE CSE 2009
Q21.
Given the following state table of an FSM with two states A and B, one input and one output: If the initial state is A = 0, B=0, what is the minimum length of an input string which will take the machine to the state A=0, B=1 with Output=1?Q22.
In the RSA public key cryptosystem, the private and public keys are (e,n) and (d,n) respectively, where n=p*q and p and q are large primes. Besides, n is public and p and q are private. Let M be an integer such that 0 \lt M \lt n and \phi (n)= (p-1)(q-1). Now consider the following equations. I. M'=M^{e} mod \; n M=(M')^{d}mod \; n II. ed=1 mod n III. ed=1 mod \phi (n) IV. M'=M^{e}mod \; \phi (n) M=(M')^{d}mod \; \phi (n) Which of the above equations correctly represent RSA cryptosystem?Q23.
Consider the following relational schema: Suppliers(sid:integer, sname:string, city:string, street:string) Parts(pid:integer, pname:string, color:string) Catalog(sid:integer, pid:integer, cost:real) Assume that, in the suppliers relation above, each supplier and each street within a city has a unique name, and (sname, city) forms a candidate key. No other functional dependencies are implied other than those implied by primary and candidate keys. Which one of the following is TRUE about the above schema?Q24.
Which of the following statements are TRUE? I There exist parsing algorithms for some programming languages whose complexities are less than \theta (n^{3}). II A programming language which allows recursion can be implemented with static storage allocation. III No L-attributed definition can be evaluated in the framework of bottom-up parsing. IV Code improving transformations can be performed at both source language and intermediate code level.Q25.
Consider a 4 stage pipeline processor. The number of cycles needed by the four instructions I1, I2, I3, I4 in stages S1, S2, S3, S4 is shown below: What is the number of cycles needed to execute the following loop? For (i=1 to 2) {I1; I2; I3; I4;}Q26.
An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The probability that the face value is odd is 90% of the probability that the face value is even. The probability of getting any even numbered face is the same. If the probability that the face is even given that it is greater than 3 is 0.75, which one of the following options is closest to the probability that the face value exceeds 3?Q27.
In the following process state transition diagram for a uniprocessor system, assume that there are always some processes in the ready state: Now consider the following statements: I. If a process makes a transition D, it would result in another process making transition A immediately. II. A process P2 in blocked state can make transition E while another process P1 is in running state. III. The OS uses preemptive scheduling. IV. The OS uses non-preemptive scheduling. Which of the above statements are TRUE?Q28.
The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows: void enter_CS(x) { while test-and-set(x) ; } void leave_CS(x) { x=0; } In the above solution, x is a memory location associated with the CS and is nitialized to 0. Now consider the following statements: I. The above solution to CS problem is deadlock-free II. The solution is starvation free. III. The processes enter CS in FIFO order. IV More than one process can enter CS at the same time. Which of the above statements is TRUE?Q29.
Which one of the following is the most appropriate logical formula to represent the statement? "Gold and silver ornaments are precious". The following notations are used: G(x): x is a gold ornament S(x): x is a silver ornament P(x): x is preciousQ30.
Consider the following well-formed formulae: I. \neg \forall x(P(x)) II. \neg \exists x(P(x)) III. \neg \exists x(\neg P(x)) IV. \exists x(\neg P(x)) Which of the above are equivalent?